package com.hh.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author hanghao
 * @Date 2023/6/27 10:51
 * @Version 1.0
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 */

public class No438 {
    public static List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> res = new ArrayList<>();
        int plen = p.length();
        int slen = s.length();
        if (plen > slen) {
            return res;
        }
        int[] precord = new int[26];
        int[] srecord = new int[26];
        //将滑动窗口放进去
        for (int i = 0; i < plen; i++) {
            precord[p.charAt(i) - 'a']++;
            srecord[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(precord,srecord)) {
            res.add(0);
        }
        //开始移动滑动窗口
        for (int i = 0; i < (slen - plen); i++) {
            --srecord[s.charAt(i) - 'a'];  //将滑动前首位的去掉
            ++srecord[s.charAt(i + plen) - 'a']; //将本次滑动新增的加上
            if(Arrays.equals(precord,srecord)) {
                res.add(i + 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> anagrams = findAnagrams(s, p);
        for (Integer anagram : anagrams) {
            System.out.println(anagram);
        }
    }
}
